1. Field of the Invention
The present invention relates to a map-data-generation device and a map-generation method used therefor, and a navigation device and a route-search method used therefor, and particularly relates to a map-data-generation device generating hierarchical guide-route-search-map data by using information about a road link of a reference level and a map-generation method used therefor, and a navigation device making a search for a route to a destination point by using the map data, and a route-search method used therefor.
2. Description of the Related Art
A navigation device reads map data generated in accordance with the current position of a vehicle from a map-storage medium including a compact disk (CD)-read only memory (ROM), a digital-versatile disk (DVD), a hard-disk drive (HDD), and so forth and produces an image of the map data on a display screen. Further, the navigation device displays a vehicle mark on the display screen at a fixed position and displays the map image in a scrolling manner according to the travel state of the vehicle. Further, the navigation device has a route-guide function, so as to make a search for a guide route extending from a departure point to a destination point and/or a guide route extending from the departure point to the destination point via a predetermined transit point, and produce an image of the guide route on the map image. There has been disclosed a method of storing information about a special-purpose mesh-to-mesh network in map data, decreasing the number of search branches by using the special-purpose network, and making the route search with high speed, as a known technology 1 which allows for making the route search with high speed (Japanese Unexamined Patent Application Publication No. 2003-337034). Further, there has been disclosed a known technology 2 which allows for making the route search with high speed by using hierarchical map data in place of the special-purpose network (Japanese Unexamined Patent Application Publication No. 2004-286524).
According to the known technology 1, five levels are provided according to the detail degree of the map, as shown in FIG. 25A, and road information of the map includes information about roads of the levels and the special-purpose-network information. A basic unit of each of the levels is configured to specify the road information corresponding to a road existing in the area corresponding to the level. Each of the expansion parts of levels 1 and 2 has an associated information part provided, so as to make a search with high speed. The special-purpose network includes route information (information about a link and/or a node) required to make a search for a route connecting arbitrary two level-2 areas to each other in association with a combination of the above-described level-2 areas.
When a departure point S is determined, as shown in FIG. 25B, a level-1 area A1 including the departure point S and a level-2 area C1 including the level-1 area A1 are determined. Likewise, when a destination point E is determined, a level-1 area A2 including the destination point and a level-2 area C2 including the level-1 area A2 are determined. Since information about the special-purpose network is provided in accordance with a combination of the two level-2 areas C1 and C2, the route search is made by using the special-purpose-network information. More specifically, information about the upper-transition nodes P11, P12, and P13 corresponding to the departure point, and the upper-transition nodes Q11, Q12, and Q13 corresponding to the destination point is extracted by using level-1-map information and expansion information of the special-purpose network. Then, a search for a plurality of routes between upper nodes N11, N12, and N13, and upper nodes M11, M12, and M13 corresponding to the upper-transition nodes is made by using special-purpose-network information (information about links and/or nodes), and a route requiring the minimum cost of all of the routes is determined to be a guide route.
According to the known technology 2, the road information is shown by using levels 1 to 4 provided so that the map data is hierarchically configured, as shown in FIG. 26. Level 1 denotes part specifying map information indicating a guide-route-object road, and a non-guide-route-object road (narrow street), level 2 denotes part specifying information about the guide-route-object road, level 3 denotes part specifying map information indicating a primary road, and level 4 denotes part specifying map information indicating a more primary road (a prefectural road, a national road, and an expressway). When the departure point S and the destination point E are determined, a node b10 making its transition from the departure point S to a level-3 upper node is obtained on level 2. Next, a node c10 making its transition from the node b10 to a level-4 upper node is obtained, and a route extending from the departure point S to the upper node c10 is obtained. Likewise, a route extending from the destination point E to an upper node C20 of the uppermost level 4 is obtained. Next, a search for a route extending from the upper node c10 on the departure-point side to the upper node c20 on the destination-point side is made by using level-4-road information. Eventually, a search for a route that extends from the departure point to the destination point and that requires the minimum cost is made.
Since the known technology 1 is achieved by using a large number of special-purpose networks, the size of road information increases. Further, when the map data is updated by generating difference data, the amount of difference data of the special-purpose-network information increases, which increases the communication time required to acquire the difference data through communications. Subsequently, the communication cost and the map-update time are increased.
According to the hierarchical route search disclosed in the known technology 2, the levels are determined on the basis of hierarchical information including information about the road type or the like. Therefore, the quality of a road obtained through the hierarchical search is lower than that of a route obtained through a search made on the lower-most level (a level where information about all of the route-guide-object roads is stored).